{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Call with Current Continuation\n",
    "\n",
    "This discussion is about continuations. We have them built into our language, `calc`, and also Scheme. Wouldn't it be cool if we could reach in and grab one?!\n",
    "\n",
    "Yes! In Scheme, continuations are **first-class objects**.\n",
    "\n",
    "## Hy Lisp Review\n",
    "\n",
    "* Hy doesn't use continuations\n",
    "* Hy uses a stack (Python's)\n",
    "* Is really just \"syntactic sugar\" for Python\n",
    "* They could implement Hy like we did Calc in Python\n",
    "* Hy does have a limited closures (Python's closures)\n",
    "\n",
    "## Scheme Review \n",
    "\n",
    "For this discussion we need to remember a couple of functions from Scheme:\n",
    "\n",
    "* `map`\n",
    "* `for-each`\n",
    "\n",
    "Recall that `map` takes a function $f$ and applies it to each item in a list:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(\"hello!\" \"there!\" \"little!\" \"bunny!\")"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(map (lambda (s) (string-append s \"!\")) '(\"hello\" \"there\" \"little\" \"bunny\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`for-each` does the same, but doesn't return the list:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "(for-each (lambda (s) (string-append s \"!\")) '(\"hello\" \"there\" \"little\" \"bunny\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So, what is for-each good for? It is good for when you are interested in a function's _side-effects_ rathern than its return value. For example, you might have a function that makes a robot move:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "(define move\n",
    "  (lambda (motion)\n",
    "    (printf \"Robot is moving ~s~%\" motion)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Robot is moving \"backward\"\n",
      "Robot is moving \"forward\"\n",
      "Robot is moving \"up and down\"\n",
      "Robot is moving \"right\"\n",
      "Robot is moving \"left\"\n"
     ]
    }
   ],
   "source": [
    "(for-each move '(\"backward\" \"forward\" \"up and down\" \"right\" \"left\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Call with Current Continuation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Consider this simple function below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "(define f\n",
    " (lambda (return)\n",
    "    (return 2)\n",
    "    3)) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What will the following give?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(f (lambda (x) x))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In fact, it doesn't really matter what return does, it can only compute something, which is ignored. \n",
    "\n",
    "But, if we pass f into call-with-current-continuation then something surprising happens:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(call-with-current-continuation f) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's look at a couple more examples:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\"One\"\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "#t"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    " (call-with-current-continuation\n",
    "    (lambda (return)\n",
    "      (begin\n",
    "        (print \"One\")\n",
    "        (return #t)\n",
    "        (print \"Two\")\n",
    "        #f)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "blue"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(call-with-current-continuation\n",
    "    (lambda (exit)\n",
    "      (map (lambda (x)\n",
    "                  (if (eq? x 'blue)\n",
    "                      (exit x)\n",
    "                      (symbol->string x)))\n",
    "                '(this is a blue bunny in your yard))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "(call-with-current-continuation\n",
    "    (lambda (exit)\n",
    "      (map (lambda (x)\n",
    "                  (if (eq? x 'blue)\n",
    "                      (exit exit)\n",
    "                      (symbol->string x)))\n",
    "                '(this is a blue bunny in your yard))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "(define generator\n",
    "  (lambda (lst)\n",
    " \n",
    "  ;; Hand the next item from a-list to \"return\" or an end-of-list marker\n",
    "  (define control-state\n",
    "   (lambda (yield)\n",
    "    (for-each \n",
    "     (lambda (element)\n",
    "               (set! yield (call-with-current-continuation\n",
    "                              (lambda (resume-here)\n",
    "                                  ;; Grab the current continuation\n",
    "                                  (set! control-state resume-here)\n",
    "                                  (yield element)))))\n",
    "     lst)\n",
    "    (yield '())))\n",
    " \n",
    "  ;; This is the actual generator, producing one item from a-list at a time\n",
    "  (define start-generator\n",
    "    (lambda ()\n",
    "      (call-with-current-continuation control-state)))\n",
    " \n",
    "  ;; Return the generator \n",
    "  start-generator))\n",
    " \n",
    "(define next\n",
    "  (generator '(0 1 2))) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(next) ;; 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(next) ;; 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(next) ;; 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "()"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(next) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`call-with-current-continuation` is a lot of typing! You can abbreviated it to `call/cc`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Consider this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#<procedure>"
      ]
     },
     "execution_count": 71,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(call/cc (lambda (k) (k k)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Time travel, again"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "(define cont #f)\n",
    "\n",
    "(begin \n",
    "  (print 1)\n",
    "  (print 2)\n",
    "\n",
    "  (set! cont (call/cc (lambda (k) (k k))))\n",
    "\n",
    "  (print 3)\n",
    "  (print 4)\n",
    " )\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "(cont cont)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "(cont cont)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "(cont (lambda (i) i))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#<procedure>"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(cont (lambda (i) i))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(+ 1 (call/cc\n",
    "       (lambda (k)\n",
    "         (+ 2 (k 3)))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(define redo #f)\n",
    "\n",
    "(+ 1 (call/cc\n",
    "       (lambda (k)\n",
    "         (set! redo k)\n",
    "         (+ 2 (k 3)))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "43"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(redo 42)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "101"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(redo 100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implementing amb, fail"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "; current-continuation : -> continuation\n",
    "(define (current-continuation) \n",
    "  (call-with-current-continuation \n",
    "   (lambda (cc)\n",
    "     (cc cc))))\n",
    "\n",
    "; fail-stack : list[continuation]\n",
    "(define fail-stack '())\n",
    "\n",
    "; fail : -> ...\n",
    "(define (fail)\n",
    "  (if (not (pair? fail-stack))\n",
    "      (error fail \"back-tracking stack exhausted!\")\n",
    "      (begin\n",
    "        (let ((back-track-point (car fail-stack)))\n",
    "          (set! fail-stack (cdr fail-stack))\n",
    "          (back-track-point back-track-point)))))\n",
    "\n",
    "; amb : list[a] -> a\n",
    "(define (amb choices)\n",
    "  (let ((cc (current-continuation)))\n",
    "    (cond\n",
    "      ((null? choices)      (fail))\n",
    "      ((pair? choices)      (let ((choice (car choices)))\n",
    "                              (set! choices (cdr choices))\n",
    "                              (set! fail-stack (cons cc fail-stack))\n",
    "                              choice)))))\n",
    "\n",
    "; (assert condition) will cause\n",
    "; condition to be true, and if there\n",
    "; is no way to make it true, then\n",
    "; it signals and error in the program.\n",
    "(define (assert condition)\n",
    "  (if (not condition)\n",
    "      (fail)\n",
    "      #t))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We're looking for dimensions of a legal right triangle using the Pythagorean theorem:\n",
    "\n",
    "$ a^2 + b^2 = c^2 $\n",
    "\n",
    "And, we want the second side (b) to be the shorter one:\n",
    "\n",
    "$ b < a $"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(4 3 5)\n"
     ]
    }
   ],
   "source": [
    "(let ((a (amb (list 1 2 3 4 5 6 7)))\n",
    "      (b (amb (list 1 2 3 4 5 6 7)))\n",
    "      (c (amb (list 1 2 3 4 5 6 7))))\n",
    "    \n",
    "  (assert (= (* c c) (+ (* a a) (* b b))))\n",
    "  (assert (< b a))\n",
    "\n",
    "  ; Print out the answer:\n",
    "  (display (list a b c))\n",
    "  (newline))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## How would you implement call/cc?"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Calysto Scheme 2",
   "language": "scheme",
   "name": "calysto_scheme"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "scheme"
   },
   "mimetype": "text/x-scheme",
   "name": "scheme",
   "pygments_lexer": "scheme"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}